
//2080.区间内查询数字的频率
class RangeFreqQuery {

    unordered_map<int,vector<int>> nums;  //存储每一个数对应的下标
public:
    RangeFreqQuery(vector<int>& arr) {
        int n=arr.size();
        for(int i=0;i<n;i++)
        nums[arr[i]].push_back(i);   //依次进行存储的，所以nums[arr[i]]本来就是有序的不需要再进行排序
    }
    
    int query(int left, int right, int value) {
        vector<int>& index=nums[value];

        //在数组中进行查找
        int start=lower_bound(index.begin(),index.end(),left)-index.begin();
        if(start==index.size()) return 0;
        int end=upper_bound(index.begin(),index.end(),right)-index.begin();

        return end-start;
    }
};
